package com.zhugang.week08;

/**
 * @program algorithms
 * @description: bag
 * @author: chanzhugang
 * @create: 2022/08/03 23:00
 */
public class Bage {

    /**
     * 0-1 背包问题（不可切割，装或者不装）
     *
     * @param items
     * @param w
     * @return
     */
    private int maxW = Integer.MIN_VALUE;

    public int bage(int[] items, int w) {
        // 回溯
        backstrack(items, 0, 0, w);
        return maxW;
    }

    /**
     * @param items 选择列表，选或者不选
     * @param k     阶段
     * @param cw    路径，记录已经选择的物品的总质量
     * @param w     剪枝的条件
     */
    private void backstrack(int[] items, int k, int cw, int w) {
        if (cw == w || k == items.length) {
            // 装满了 或者 考察完了所有物品
            if (cw > maxW) {
                maxW = cw;
            }
            return;
        }
        // 做选择，不装
        backstrack(items, k + 1, cw, w);

        if (cw + items[k] <= w) {
            // 剪枝
            // 装
            backstrack(items, k + 1, cw + items[k], w);
            // 都是局部变量，不需要撤销
        }
    }
}